package cn.kingshion.sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

public class QuickSort {
    private static int count;

    public static void main(String[] args) {
        //随机化一个大容量的数组。
        //用来测试冒泡排序的效率
        int arr[] = new int[80000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * 80000);
        }

        //定义一个时间对象，用来表示数组排序前的时间
        Date date1 = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        System.out.println("排序前：" + simpleDateFormat.format(date1));
        //排序数组
        quickSort(arr, 0, arr.length - 1);

        System.out.println(Arrays.toString(arr));
        //新的时间，打印出排序完的时间
        Date date2 = new Date();
        System.out.println("排序前：" + simpleDateFormat.format(date2));


    }

    public static void quickSort(int[] arr, int left, int right) {
        // 如果 left 等于 right，即数组只有一个元素，直接返回
        if (left >= right) return;
        //设置最左边的元素为基准值
        int key = arr[left];
        //数组中比key小的放在左边，比key大的放在右边，key值下标为l
        int l = left;
        int r = right;
        // 两个指针从两端向中间遍历，每次都会跟 基准值 key 进行比较，
        while (l < r) {
            // 如果 r 的值大于 key 基准值，那么 r 向左移动 ——
            while (l < r && arr[r] > key) r--;

            // 如果 l 的值小于 key 基准值，那么 l 向右移动 ++
            while (l < r && arr[l] <= key) l++;

            // 这两个数是处于 key 基准值两边的。
            // 交换位置后 才满足需要的 顺序
            int temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;
        }
        // 将当前的 i下标对应的值与 之前的 key 基准值进行交换
        arr[left] = arr[l];
        arr[l] = key;
        //继续递归调用该方法
        quickSort(arr, left, l - 1);
        quickSort(arr, l + 1, right);

    }

}
